import random

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n=len(s)
        if n<2:
            return s
        start = 0
        max_len = 1
        dp=[[False]*n for _ in range(n)]
        for i in range(n):
            dp[i][i]= True
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                start = i
                max_len = 2
        for length in range(3,n+1):
            for i in range(n - length + 1):
                j= i + length - 1
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    start = i
                    max_len = length
        return s[start:start+max_len]

def generate_palindrome_test_data(min_length=1, max_length=100, num_cases=10):
    test_cases = []

    # 添加空字符串
    test_cases.append("")

    for _ in range(num_cases):
        # 生成随机长度的字符串
        length = random.randint(min_length, max_length)
        # 生成随机字符串
        rand_string = ''.join(random.choices('abcdefghijklmnopqrstuvwxyz', k=length))
        # 随机选择回文子串的起始位置
        start_index = random.randint(0, length - 1)
        # 选择子串长度
        pal_length = random.randint(1, min(length - start_index, 20))
        # 构建回文子串
        palindrome = rand_string[start_index:start_index + pal_length] + rand_string[start_index::-1]
        # 将回文子串插入到随机位置
        rand_index = random.randint(0, len(rand_string))
        test_cases.append(rand_string[:rand_index] + palindrome + rand_string[rand_index:])

    return test_cases

# 生成测试数据
test_data = generate_palindrome_test_data()

# 创建解决方案对象
solution = Solution()

# 测试解决方案
for i, case in enumerate(test_data):
    result = solution.longestPalindrome(case)
    print(f"Test case {i+1}: Input - '{case}', Output - '{result}'")
